---
title: "698. Partition to K Equal Sum Subsets"
created: 2025-12-20
---
# 698. Partition to K Equal Sum Subsets

**📑 目录**

- [题目 698. Partition to K Equal Sum Subsets](#toc-1766820458598-0)
- [思路分析](#toc-1766820458598-1)
- [代码实现](#toc-1766820458598-2)
- [同类题型](#toc-1766820458598-3)
- [视频讲解](#toc-1766820458598-4)

## 题目 [**698. Partition to K Equal Sum Subsets**](https://leetcode.com/problems/partition-to-k-equal-sum-subsets/)

![[image-9b930ef0.png]]

## 思路分析

![[image-c44de85d.png]]

## 代码实现

```java
import java.util.Arrays;

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = 0;
        for (int num : nums) sum += num;
        if (sum % k != 0) return false;

        int target = sum / k;

        Arrays.sort(nums);
        if (nums[nums.length - 1] > target) return false;

        boolean[] used = new boolean[nums.length];

        return backtrack(nums, k, 0, nums.length - 1, 0, target, used);
    }

    // k: 还需要拼凑多少个桶
    // curBucketSum: 当前桶已经装了多少
    // start: 从nums的哪个索引开始尝试(避免重复枚举)
    private boolean backtrack(int[] nums, int k, int curBucketSum, int start, int count, int target, boolean[] used) {
        // base case: 如果 k 个桶都装满了（实际上只需要装满 k-1 个，最后一个自然就满了）
        // 这里写 k==0 或者 k==1 都可以作为终止条件
        if (k == 0) return true;

        // 如果当前桶装满了，开始装下一个桶 (k-1)，重置 sum 和 start
        if (curBucketSum == target) {
            return backtrack(nums, k - 1, 0, nums.length - 1, 0, target, used);
        }

        for (int i = start; i >= 0; i--) {
            if (used[i] || curBucketSum + nums[i] > target) continue;

            used[i] = true;
            if (backtrack(nums, k, curBucketSum + nums[i], i - 1, count + 1, target, used)) {
                return true;
            }
            used[i] = false;

            // --- 核心剪枝 (Pruning) ---
            // 1. 如果当前桶是空的，且尝试放入 nums[i] 失败了。
            //    说明 nums[i] 无法作为任何一个新桶的开头（因为所有空桶都是等价的）。
            //    既然它无论如何都放不进新桶，那整个问题无解，直接剪枝。
            if (curBucketSum == 0) return false;

            // 2. 如果当前桶加上 nums[i] 恰好满了，但后续递归失败了。
            //    说明 nums[i] 虽然能凑成 target，但会导致剩下的数字无解。
            //    由于这是凑成 target 的最后一步，没有比这更完美的情况了，没必要试更小的数，直接剪枝。
            if (curBucketSum + nums[i] == target) return false;

            // 3. 去重剪枝：如果当前数字和前一个数字相同，且前一个数字没被用过（说明前一个数字刚才试过失败了）
            //    那当前数字肯定也失败，跳过。
            while (i > 0 && nums[i] == nums[i-1] && !used[i-1]) {
                i--;
            }
        }

        return false;
    }
}
```

## 同类题型

## 视频讲解